package codeTopPractice;

/**
 * @LeetCode 第 206 题
 *
 * 给你   单链表的头节点，请你将其进行反转，并返回反转后的链表
 * Definition for singly-linked list.   单链表的定义
 *  public class ListNode {
 *      int val;            该链表节点的值
 *      ListNode next;      指向的下一个节点
 *      ListNode() {}       无参构造函数
 *      ListNode(int val) { this.val = val; }   赋值构造函数
 *      ListNode(int val, ListNode next) { this.val = val; this.next = next; }   赋值该节点并有指向下一节点的构造函数
 *  }
 *
 *  思路：
 *      解法一:
 *        使用双指针（当前指针curr，前指针pre），加一个临时指针（temp）
 *        首先判断传入的参数head是否为空，为空则直接返回空值；
 *        创建三个节点，将pre赋值null，curr赋值为head；
 *        以curr的当前节点值不为空作为条件进行while循环，
 *        不为空时：
 *          1.将curr的下一节点赋值给临时指针temp
 *          2.将pre赋值到curr的下一节点
 *          3.将curr赋值给pre（pre往前一位）
 *          4.将temp赋值给curr（curr往前一位）
 *         为空时：
 *              返回pre；
 *
 *       解法2：
 *          使用递归
 *          以当前节点或其下一个节点是否为空作为条件进行递归，递归只链表最后一个节点并赋值给新创建的链表变量作为头结点
 *          并依进行处理
 *                  head.next.next = head;
 *                  head.next = null;
 *          最后返回头结点
 *
 *
 */


public class 反转链表 {

    // 测试
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2,listNode1);
        ListNode head = new ListNode(3,listNode2);
        System.out.println(outFormat(head));
        System.out.println(outFormat(reverseListRecursion(head)));

    }

    // 解法一 双指针加临时指针
    public static ListNode reverseListTwoPoints(ListNode head) {
        if(head == null){
            return head;
        }

        ListNode curr;
        ListNode pre = null;
        ListNode temp;
        curr = head;
        while(curr != null){
            temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr=temp;
        }

        return pre;
    }

    // 解法二 递归
    public static ListNode reverseListRecursion(ListNode head){
        if(head == null || head.next == null){
            return head;
        }


        ListNode p = reverseListRecursion(head.next);
        head.next.next = head;
        head.next = null;
        return p;

     }

    // 链表节点类
    public static class ListNode {
         int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        public int length(){
            int len = 0;
            ListNode listNode = this;
            while (listNode != null){
                len++;
                listNode = listNode.next;

            }

            return len;
        }
    }

    // 输出格式
    public static StringBuilder outFormat(ListNode listNode){
        StringBuilder str = new StringBuilder("[");

        int length = listNode.length();

        for (int i = 0; i <length; i++) {
            if(i == length-1){
                str.append(listNode.val+"]");
            }else {
                str.append(listNode.val+",");
            }
            listNode = listNode.next;
        }

        return str;
    }


}


